//请实现一个函数，把字符串 s 中的每个空格替换成"%20"。 
// 示例 1：
// 输入：s = "We are happy."
//输出："We%20are%20happy." 
// 限制：
// 0 <= s 的长度 <= 10000
// Related Topics 字符串 👍 247 👎 0

package leetcode.editor.offer;

// 剑指 Offer 05. 替换空格
class TiHuanKongGeLcof {
    public static void main(String[] args) {
        Solution solution = new TiHuanKongGeLcof().new Solution();
        solution.replaceSpace("We are happy.");
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 双指针法
         *
         * @param s
         * @return
         */
    /*public String replaceSpace(String s) {
        if (s == null && s.length() == 0) {
            return null;
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == ' ') {   // 有空格就添加2个字符
                sb.append("  ");
            }
        }

        if (sb.length() == 0) {
            return s;
        }

        int left = s.length();  // 指向原来字符串的末尾
        s += sb;
        int right = s.length(); // 扩充了的末尾
        char[] array = s.toCharArray();

        while (left >= 0) {
            if (array[left] == ' ') {   // 扩充在后边
                array[right--] = '0';
                array[right--] = '2';
                array[right] = '%';
            } else {
                array[right] = array[left];
            }
            left--;
            right--;
        }

        return new String(array);
    }*/

        /**
         * 使用多余的空间，赋值法
         *
         * @param s
         * @return
         */
//        public String replaceSpace(String s) {
//            if (s == null) {
//                return s;
//            }
//
//            StringBuilder sb = new StringBuilder();
//            for (int i = 0; i < s.length(); i++) {
//                if (s.charAt(i) == ' ') {
//                    sb.append("%20");
//                } else {
//                    sb.append(s.charAt(i));
//                }
//            }
//            return String.valueOf(sb);
//        }
        public String replaceSpace(String s) {
            if (s == null && s.length() == 0) {
                return null;
            }
            StringBuilder sb = new StringBuilder(s);
            int n = s.length();
            for (int i = 0; i < n; i++) {
                if (s.charAt(i) == ' ') {
                    sb.append("  ");
                }
            }

            char[] newArr = sb.toString().toCharArray();

            int l = n - 1, r = newArr.length - 1;
            while (l >= 0) {
                if (newArr[l] == ' ') {
                    newArr[r--] = '0';
                    newArr[r--] = '2';
                    newArr[r] = '%';
                } else {
                    newArr[r] = newArr[l];
                }

                l--;
                r--;
            }

            return new String(newArr);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
